public class Solution5 {

    private boolean isLocEquals(String s, int i, int j){
        return s.charAt(i) == s.charAt(j);
    }

    public String longestPalindrome(String s) {
        int len = s.length();
        int[][] dpArr = new int[len][len];
        int maxLen = 0, start = 0, end = 0;
        for (int i = len - 1; i >= 0 ; i--) {
            for (int j = i; j < len; j++) {
                int tmpLen = 0;
                if(i == j){
                    tmpLen = 1;
                }
                else if(i == j - 1){
                    if(isLocEquals(s, i, j)){
                        tmpLen = 2;
                    }
                }
                else{
                    int lastNum = dpArr[i + 1][j - 1];
                    if(lastNum != 0 && isLocEquals(s, i, j)){
                        tmpLen = lastNum + 2;
                    }
                }
                dpArr[i][j] = tmpLen;
                if(tmpLen > maxLen){
                    start = i;
                    end = j;
                    maxLen = tmpLen;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}
